home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / a_utils / perl / msds-prl / dpmi.taz / dpmi / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-12  |  13.5 KB  |  521 lines
  1. /* $RCSfile: malloc.c $$Revision: 1.1 $$Date: 92/11/10 10:43:56 $
  2.  *
  3.  * [ Marc Pawlowsky, November 1992 ]
  4.  *  Modified for High C, to skip the whole thing and leave malloc
  5.  *  alone.
  6.  * 
  7.  * Revision 4.0.1.4  92/06/08  14:28:38  lwall
  8.  * patch20: removed implicit int declarations on functions
  9.  * patch20: hash tables now split only if the memory is available to do so
  10.  * patch20: realloc(0, size) now does malloc in case library routines call it
  11.  * 
  12.  * Revision 4.0.1.3  91/11/05  17:57:40  lwall
  13.  * patch11: safe malloc code now integrated into Perl's malloc when possible
  14.  * 
  15.  * Revision 4.0.1.2  91/06/07  11:20:45  lwall
  16.  * patch4: many, many itty-bitty portability fixes
  17.  * 
  18.  * Revision 4.0.1.1  91/04/11  17:48:31  lwall
  19.  * patch1: Configure now figures out malloc ptr type
  20.  * 
  21.  * Revision 4.0  91/03/20  01:28:52  lwall
  22.  * 4.0 baseline.
  23.  * 
  24.  */
  25.  
  26. #ifndef lint
  27. /*SUPPRESS 592*/
  28. static char sccsid[] = "@(#)malloc.c    4.3 (Berkeley) 9/16/83";
  29.  
  30. /* Skip the whole thing for HIGH C, since it does a pretty
  31.    good job, and this file would not compile.
  32.  
  33.    Probably since caddr_t is not defined anywhere.
  34. */  
  35. #ifndef __HIGHC__
  36.  
  37. #ifdef DEBUGGING
  38. #define RCHECK
  39. #endif
  40. /*
  41.  * malloc.c (Caltech) 2/21/82
  42.  * Chris Kingsley, kingsley@cit-20.
  43.  *
  44.  * This is a very fast storage allocator.  It allocates blocks of a small 
  45.  * number of different sizes, and keeps free lists of each size.  Blocks that
  46.  * don't exactly fit are passed up to the next larger size.  In this 
  47.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  48.  * This is designed for use in a program that uses vast quantities of memory,
  49.  * but bombs when it runs out. 
  50.  */
  51.  
  52. #include "EXTERN.h"
  53. #include "perl.h"
  54.  
  55. static findbucket(), morecore();
  56.  
  57. /* I don't much care whether these are defined in sys/types.h--LAW */
  58.  
  59. #define u_char unsigned char
  60. #define u_int unsigned int
  61. #define u_short unsigned short
  62.  
  63. /*
  64.  * The overhead on a block is at least 4 bytes.  When free, this space
  65.  * contains a pointer to the next free block, and the bottom two bits must
  66.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  67.  * byte is the size index.  The remaining bytes are for alignment.
  68.  * If range checking is enabled and the size of the block fits
  69.  * in two bytes, then the top two bytes hold the size of the requested block
  70.  * plus the range checking words, and the header word MINUS ONE.
  71.  */
  72. union    overhead {
  73.     union    overhead *ov_next;    /* when free */
  74. #if ALIGNBYTES > 4
  75.     double    strut;            /* alignment problems */
  76. #endif
  77.     struct {
  78.         u_char    ovu_magic;    /* magic number */
  79.         u_char    ovu_index;    /* bucket # */
  80. #ifdef RCHECK
  81.         u_short    ovu_size;    /* actual block size */
  82.         u_int    ovu_rmagic;    /* range magic number */
  83. #endif
  84.     } ovu;
  85. #define    ov_magic    ovu.ovu_magic
  86. #define    ov_index    ovu.ovu_index
  87. #define    ov_size        ovu.ovu_size
  88. #define    ov_rmagic    ovu.ovu_rmagic
  89. };
  90.  
  91. #define    MAGIC        0xff        /* magic # on accounting info */
  92. #define OLDMAGIC    0x7f        /* same after a free() */
  93. #define RMAGIC        0x55555555    /* magic # on range info */
  94. #ifdef RCHECK
  95. #define    RSLOP        sizeof (u_int)
  96. #else
  97. #define    RSLOP        0
  98. #endif
  99.  
  100. /*
  101.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  102.  * smallest allocatable block is 8 bytes.  The overhead information
  103.  * precedes the data area returned to the user.
  104.  */
  105. #define    NBUCKETS 30
  106. static    union overhead *nextf[NBUCKETS];
  107. extern    char *sbrk();
  108.  
  109. #ifdef MSTATS
  110. /*
  111.  * nmalloc[i] is the difference between the number of mallocs and frees
  112.  * for a given block size.
  113.  */
  114. static    u_int nmalloc[NBUCKETS];
  115. #include <stdio.h>
  116. #endif
  117.  
  118. #ifdef debug
  119. #define    ASSERT(p)   if (!(p)) botch("p"); else
  120. static void
  121. botch(s)
  122.     char *s;
  123. {
  124.  
  125.     printf("assertion botched: %s\n", s);
  126.     abort();
  127. }
  128. #else
  129. #define    ASSERT(p)
  130. #endif
  131.  
  132. #ifdef safemalloc
  133. static int an = 0;
  134. #endif
  135.  
  136. MALLOCPTRTYPE *
  137. malloc(nbytes)
  138.     register MEM_SIZE nbytes;
  139. {
  140.       register union overhead *p;
  141.       register int bucket = 0;
  142.       register MEM_SIZE shiftr;
  143.  
  144. #ifdef safemalloc
  145. #ifdef DEBUGGING
  146.     MEM_SIZE size = nbytes;
  147. #endif
  148.  
  149. #ifdef MSDOS
  150.     if (nbytes > 0xffff) {
  151.         fprintf(stderr, "Allocation too large: %lx\n", (long)nbytes);
  152.         exit(1);
  153.     }
  154. #endif /* MSDOS */
  155. #ifdef DEBUGGING
  156.     if ((long)nbytes < 0)
  157.         fatal("panic: malloc");
  158. #endif
  159. #endif /* safemalloc */
  160.  
  161.     /*
  162.      * Convert amount of memory requested into
  163.      * closest block size stored in hash buckets
  164.      * which satisfies request.  Account for
  165.      * space used per block for accounting.
  166.      */
  167.       nbytes += sizeof (union overhead) + RSLOP;
  168.       nbytes = (nbytes + 3) &~ 3; 
  169.       shiftr = (nbytes - 1) >> 2;
  170.     /* apart from this loop, this is O(1) */
  171.       while (shiftr >>= 1)
  172.           bucket++;
  173.     /*
  174.      * If nothing in hash bucket right now,
  175.      * request more memory from the system.
  176.      */
  177.       if (nextf[bucket] == NULL)    
  178.           morecore(bucket);
  179.       if ((p = (union overhead *)nextf[bucket]) == NULL) {
  180. #ifdef safemalloc
  181.         if (!nomemok) {
  182.             fputs("Out of memory!\n", stderr);
  183.             exit(1);
  184.         }
  185. #else
  186.           return (NULL);
  187. #endif
  188.     }
  189.  
  190. #ifdef safemalloc
  191. #ifdef DEBUGGING
  192. #  if !(defined(I286) || defined(atarist))
  193.     if (debug & 128)
  194.         fprintf(stderr,"0x%x: (%05d) malloc %ld bytes\n",p+1,an++,(long)size);
  195. #  else
  196.     if (debug & 128)
  197.         fprintf(stderr,"0x%lx: (%05d) malloc %ld bytes\n",p+1,an++,(long)size);
  198. #  endif
  199. #endif
  200. #endif /* safemalloc */
  201.  
  202.     /* remove from linked list */
  203. #ifdef RCHECK
  204.     if (*((int*)p) & (sizeof(union overhead) - 1))
  205. #if !(defined(I286) || defined(atarist))
  206.         fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
  207. #else
  208.         fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
  209. #endif
  210. #endif
  211.       nextf[bucket] = p->ov_next;
  212.     p->ov_magic = MAGIC;
  213.     p->ov_index= bucket;
  214. #ifdef MSTATS
  215.       nmalloc[bucket]++;
  216. #endif
  217. #ifdef RCHECK
  218.     /*
  219.      * Record allocated size of block and
  220.      * bound space with magic numbers.
  221.      */
  222.       if (nbytes <= 0x10000)
  223.         p->ov_size = nbytes - 1;
  224.     p->ov_rmagic = RMAGIC;
  225.       *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  226. #endif
  227.       return ((MALLOCPTRTYPE *)(p + 1));
  228. }
  229.  
  230. /*
  231.  * Allocate more memory to the indicated bucket.
  232.  */
  233. static
  234. morecore(bucket)
  235.     register int bucket;
  236. {
  237.       register union overhead *op;
  238.       register int rnu;       /* 2^rnu bytes will be requested */
  239.       register int nblks;     /* become nblks blocks of the desired size */
  240.     register MEM_SIZE siz;
  241.  
  242.       if (nextf[bucket])
  243.           return;
  244.     /*
  245.      * Insure memory is allocated
  246.      * on a page boundary.  Should
  247.      * make getpageize call?
  248.      */
  249. #ifndef atarist /* on the atari we dont have to worry about this */
  250.       op = (union overhead *)sbrk(0);
  251. #ifndef I286
  252.       if ((int)op & 0x3ff)
  253.           (void)sbrk(1024 - ((int)op & 0x3ff));
  254. #else
  255.     /* The sbrk(0) call on the I286 always returns the next segment */
  256. #endif
  257. #endif /* atarist */
  258.  
  259. #if !(defined(I286) || defined(atarist))
  260.     /* take 2k unless the block is bigger than that */
  261.       rnu = (bucket <= 8) ? 11 : bucket + 3;
  262. #else
  263.     /* take 16k unless the block is bigger than that 
  264.        (80286s like large segments!), probably good on the atari too */
  265.       rnu = (bucket <= 11) ? 14 : bucket + 3;
  266. #endif
  267.       nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  268.       if (rnu < bucket)
  269.         rnu = bucket;
  270.     op = (union overhead *)sbrk(1L << rnu);
  271.     /* no more room! */
  272.       if ((int)op == -1)
  273.           return;
  274.     /*
  275.      * Round up to minimum allocation size boundary
  276.      * and deduct from block count to reflect.
  277.      */
  278. #ifndef I286
  279.       if ((int)op & 7) {
  280.           op = (union overhead *)(((MEM_SIZE)op + 8) &~ 7);
  281.           nblks--;
  282.       }
  283. #else
  284.     /* Again, this should always be ok on an 80286 */
  285. #endif
  286.     /*
  287.      * Add new memory allocated to that on
  288.      * free list for this hash bucket.
  289.      */
  290.       nextf[bucket] = op;
  291.       siz = 1 << (bucket + 3);
  292.       while (--nblks > 0) {
  293.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  294.         op = (union overhead *)((caddr_t)op + siz);
  295.       }
  296. }
  297.  
  298. void
  299. free(mp)
  300.     MALLOCPTRTYPE *mp;
  301. {   
  302.       register MEM_SIZE size;
  303.     register union overhead *op;
  304.     char *cp = (char*)mp;
  305.  
  306. #ifdef safemalloc
  307. #ifdef DEBUGGING
  308. #  if !(defined(I286) || defined(atarist))
  309.     if (debug & 128)
  310.         fprintf(stderr,"0x%x: (%05d) free\n",cp,an++);
  311. #  else
  312.     if (debug & 128)
  313.         fprintf(stderr,"0x%lx: (%05d) free\n",cp,an++);
  314. #  endif
  315. #endif
  316. #endif /* safemalloc */
  317.  
  318.       if (cp == NULL)
  319.           return;
  320.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  321. #ifdef debug
  322.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  323. #else
  324.     if (op->ov_magic != MAGIC) {
  325.         warn("%s free() ignored",
  326.             op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
  327.         return;                /* sanity */
  328.     }
  329.     op->ov_magic = OLDMAGIC;
  330. #endif
  331. #ifdef RCHECK
  332.       ASSERT(op->ov_rmagic == RMAGIC);
  333.     if (op->ov_index <= 13)
  334.         ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  335. #endif
  336.       ASSERT(op->ov_index < NBUCKETS);
  337.       size = op->ov_index;
  338.     op->ov_next = nextf[size];
  339.       nextf[size] = op;
  340. #ifdef MSTATS
  341.       nmalloc[size]--;
  342. #endif
  343. }
  344.  
  345. /*
  346.  * When a program attempts "storage compaction" as mentioned in the
  347.  * old malloc man page, it realloc's an already freed block.  Usually
  348.  * this is the last block it freed; occasionally it might be farther
  349.  * back.  We have to search all the free lists for the block in order
  350.  * to determine its bucket: 1st we make one pass thru the lists
  351.  * checking only the first block in each; if that fails we search
  352.  * ``reall_srchlen'' blocks in each list for a match (the variable
  353.  * is extern so the caller can modify it).  If that fails we just copy
  354.  * however many bytes was given to realloc() and hope it's not huge.
  355.  */
  356. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  357.  
  358. MALLOCPTRTYPE *
  359. realloc(mp, nbytes)
  360.     MALLOCPTRTYPE *mp; 
  361.     MEM_SIZE nbytes;
  362. {   
  363.       register MEM_SIZE onb;
  364.     union overhead *op;
  365.       char *res;
  366.     register int i;
  367.     int was_alloced = 0;
  368.     char *cp = (char*)mp;
  369.  
  370. #ifdef safemalloc
  371. #ifdef DEBUGGING
  372.     MEM_SIZE size = nbytes;
  373. #endif
  374.  
  375. #ifdef MSDOS
  376.     if (nbytes > 0xffff) {
  377.         fprintf(stderr, "Reallocation too large: %lx\n", size);
  378.         exit(1);
  379.     }
  380. #endif /* MSDOS */
  381.     if (!cp)
  382.         return malloc(nbytes);
  383. #ifdef DEBUGGING
  384.     if ((long)nbytes < 0)
  385.         fatal("panic: realloc");
  386. #endif
  387. #endif /* safemalloc */
  388.  
  389.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  390.     if (op->ov_magic == MAGIC) {
  391.         was_alloced++;
  392.         i = op->ov_index;
  393.     } else {
  394.         /*
  395.          * Already free, doing "compaction".
  396.          *
  397.          * Search for the old block of memory on the
  398.          * free list.  First, check the most common
  399.          * case (last element free'd), then (this failing)
  400.          * the last ``reall_srchlen'' items free'd.
  401.          * If all lookups fail, then assume the size of
  402.          * the memory block being realloc'd is the
  403.          * smallest possible.
  404.          */
  405.         if ((i = findbucket(op, 1)) < 0 &&
  406.             (i = findbucket(op, reall_srchlen)) < 0)
  407.             i = 0;
  408.     }
  409.     onb = (1L << (i + 3)) - sizeof (*op) - RSLOP;
  410.     /* avoid the copy if same size block */
  411.     if (was_alloced &&
  412.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
  413. #ifdef RCHECK
  414.         /*
  415.          * Record new allocated size of block and
  416.          * bound space with magic numbers.
  417.          */
  418.         if (op->ov_index <= 13) {
  419.             /*
  420.              * Convert amount of memory requested into
  421.              * closest block size stored in hash buckets
  422.              * which satisfies request.  Account for
  423.              * space used per block for accounting.
  424.              */
  425.             nbytes += sizeof (union overhead) + RSLOP;
  426.             nbytes = (nbytes + 3) &~ 3; 
  427.             op->ov_size = nbytes - 1;
  428.             *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
  429.         }
  430. #endif
  431.         res = cp;
  432.     }
  433.     else {
  434.         if ((res = (char*)malloc(nbytes)) == NULL)
  435.             return (NULL);
  436.         if (cp != res)            /* common optimization */
  437.             Copy(cp, res, (MEM_SIZE)(nbytes<onb?nbytes:onb), char);
  438.         if (was_alloced)
  439.             free(cp);
  440.     }
  441.  
  442. #ifdef safemalloc
  443. #ifdef DEBUGGING
  444. #  if !(defined(I286) || defined(atarist))
  445.     if (debug & 128) {
  446.         fprintf(stderr,"0x%x: (%05d) rfree\n",res,an++);
  447.         fprintf(stderr,"0x%x: (%05d) realloc %ld bytes\n",res,an++,(long)size);
  448.     }
  449. #  else
  450.     if (debug & 128) {
  451.         fprintf(stderr,"0x%lx: (%05d) rfree\n",res,an++);
  452.         fprintf(stderr,"0x%lx: (%05d) realloc %ld bytes\n",res,an++,(long)size);
  453.     }
  454. #  endif
  455. #endif
  456. #endif /* safemalloc */
  457.       return ((MALLOCPTRTYPE*)res);
  458. }
  459.  
  460. /*
  461.  * Search ``srchlen'' elements of each free list for a block whose
  462.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  463.  * Return bucket number, or -1 if not found.
  464.  */
  465. static int
  466. findbucket(freep, srchlen)
  467.     union overhead *freep;
  468.     int srchlen;
  469. {
  470.     register union overhead *p;
  471.     register int i, j;
  472.  
  473.     for (i = 0; i < NBUCKETS; i++) {
  474.         j = 0;
  475.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  476.             if (p == freep)
  477.                 return (i);
  478.             j++;
  479.         }
  480.     }
  481.     return (-1);
  482. }
  483.  
  484. #ifdef MSTATS
  485. /*
  486.  * mstats - print out statistics about malloc
  487.  * 
  488.  * Prints two lines of numbers, one showing the length of the free list
  489.  * for each size category, the second showing the number of mallocs -
  490.  * frees for each size category.
  491.  */
  492. void
  493. mstats(s)
  494.     char *s;
  495. {
  496.       register int i, j;
  497.       register union overhead *p;
  498.       int totfree = 0,
  499.       totused = 0;
  500.  
  501.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  502.       for (i = 0; i < NBUCKETS; i++) {
  503.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  504.               ;
  505.           fprintf(stderr, " %d", j);
  506.           totfree += j * (1 << (i + 3));
  507.       }
  508.       fprintf(stderr, "\nused:\t");
  509.       for (i = 0; i < NBUCKETS; i++) {
  510.           fprintf(stderr, " %d", nmalloc[i]);
  511.           totused += nmalloc[i] * (1 << (i + 3));
  512.       }
  513.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  514.         totused, totfree);
  515. }
  516. #endif
  517. #endif /* lint */
  518.  
  519.  
  520. #endif /* __HIGHC__ */
  521.